<html>
<head>
<title>C++ Annotations Version 6.5.0</title>
</head>
<body text="black" bgcolor="white">
<hr>
<ul>
    <li> <a href="cplusplus.html">Table of Contents</a>
    <li> <a href="cplusplus17.html">Previous Chapter</a>
    <li> <a href="cplusplus19.html">Next Chapter</a>
</ul>
<hr>
<a name="TEMPLATES"></a><a name="l320"></a>
<h1>Chapter 18: Template functions</h1>
<a name="templates"></a>
<blockquote>
    <em>
        Don't hesitate to send in feedback: send an e-mail if you like the
        C++ Annotations; if you think that important material was omitted;
        if you find errors or typos in the text or the code examples;
        or if you just feel like e-mailing. Send your e-mail to
        <a href="mailto:f.b.brokken@rug.nl">Frank B. Brokken</a>.
<p>
<strong>Please</strong> state the document version you're referring to, as found in
        the title (in this document: 6.5.0) and please state chapter and
        paragraph name or number you're referring to.
<p>
All received mail is processed conscientiously, and received
        suggestions for improvements will usually have been processed by the
        time a new version of the Annotations is released. Except for the
        incidental case I will normally not acknowledge the receipt of
        suggestions for improvements. Please don't interpret this as me not
        appreciating your efforts.
    </em>
</blockquote>
<p>

<a name="templatefunctions/intro"></a><strong>C++</strong> supports syntactical constructs allowing programmers to define and use
completely general (or abstract) functions or classes, based on generic types
and/or (possibly inferred) constant values. In the chapters on abstract
containers (chapter <a href="cplusplus12.html#Containers">12</a>) and the <code>STL</code> (chapter <a href="cplusplus17.html#STL">17</a>) we've
already used these constructs, commonly known as the <a name="an2532"></a>
<em>template mechanism</em>.
<p>
The template mechanism allows us to specify classes and algorithms,
fairly independently of the actual types for which the templates will
eventually be used. Whenever the template is used, the compiler will generate
code, tailored to the particular data type(s) used with the template. This
code is generated <a name="an2533"></a>
compile-time from the template's definition. The piece of
generated code is called an <a name="an2534"></a>
<em>instantiation</em> of the template.
<p>
In this chapter the syntactical peculiarities of templates will be covered.
The notions of <em>template type parameter</em>, <em>template non-type parameter</em>,
and <a name="an2535"></a>
<em>template function</em> will be introduced, and several examples of
templates will be offered, both in this chapter and in chapter <a href="cplusplus20.html#CONCRETE">20</a>,
providing concrete examples of <strong>C++</strong>. Template <em>classes</em>
    <a name="an2536"></a>
 are covered in chapter <a href="cplusplus19.html#TEMPCLASS">19</a>.
<p>
Templates offered standard by the language already cover containers allowing
us to construct both highly complex and standard data structures commonly used
in computer science. Furthermore, the <code>string</code> (chapter <a href="cplusplus04.html#String">4</a>) and
stream (chapter <a href="cplusplus05.html#IOStreams">5</a>) classes are commonly implemented using
templates. So, templates play a central role in present-day <strong>C++</strong>, and
should absolutely not be considered an esoteric feature of the language.
<p>
Templates should be approached somewhat similarly as generic algorithms:
they're a <a name="an2537"></a>
<em>way of life</em>; a <strong>C++</strong> software engineer should actively look
for opportunities to use them.  Initially, templates appear to be rather
complex, and you might be tempted to turn your back on them. However, in time
their strengths and benefits will be more and more appreciated. Eventually
you'll be able to recognize opportunities for using templates. That's the time
where your efforts should no longer focus on constructing concrete
        <a name="an2538"></a>

        <a name="an2539"></a>

    (i.e., non-template) functions or classes, but on constructing templates.
<p>
This chapter starts by introducing <em>template functions</em>. The emphasis is on
the required syntax when defining such functions. This chapter lays the
foundation upon which the next chapter, introducing template classes and
offering several real-life examples, is built.
<p>
<a name="TEMPFUNDEF"></a><a name="l321"></a>
<h2>18.1: Defining template functions</h2>
<a name="templatefunctions/definitions"></a>A <a name="an2540"></a>
template function's definition is very similar to the definition of
a normal function. A template function has a function head, a function body, a
return type, possibly overloaded definitions, etc.. However, different from
concrete functions, template functions always use one or more
        <a name="an2541"></a>
<em>formal types</em>:
    types for which almost any exising (class or primitive) type could be
used. Let's start with a simple example. The following function <code>add()</code>
expects two arguments, and returns their sum:
        <pre>
    Type add(Type const &amp;lvalue, Type const &amp;rvalue)
    {
        return lvalue + rvalue;
    }
</pre>
    Note how closely the above function's definition follows its description:
it gets two arguments, and returns its sum. Now consider what would happen if
we would have to define this function for, e.g., <code>int</code> values. We would have
to define:
        <pre>
    int add(int const &amp;lvalue, int const &amp;rvalue)
    {
        return lvalue + rvalue;
    }
</pre>
    So far, so good. However, were we to add to doubles, we would have to
overload this function so that its overloaded version accepts doubles:
        <pre>
    double add(double const &amp;lvalue, double const &amp;rvalue)
    {
        return lvalue + rvalue;
    }
</pre>
    There is no end to the number of overloaded versions we might be
forced to construct: an overloaded version for <code>std::string</code>, for
<code>size_t</code>, for .... In general, we would need an overloaded version for
every type supporting <code>operator+()</code> and a copy constructor. All these
overloaded versions of basically the same function are required because of the
<a name="an2542"></a>
strongly typed nature of <strong>C++</strong>. Because of this, a truly generic function
cannot be constructed without resorting to the <a name="an2543"></a>
template mechanism.
<p>
Fortunately, we've already seen the meat and bones of a template
function. Our initial function <code>add()</code> actually is an implementation of such
a function. However, it isn't a full template definition yet. If we would give
the first <code>add()</code> function to the compiler, it would produce an error
message like:
        <pre>
    error: `Type' was not declared in this scope
    error: parse error before `const'
</pre>
    And rightly so, as we failed to define <code>Type</code>. The error is prevented
when we change <code>add()</code> into a full template definition. To do this, we look
at the function's implementation and decide that <code>Type</code> is actually a
<em>formal</em> typename. Comparing it to the alternate implementations, it will be
clear that we could have changed <code>Type</code> into <code>int</code> to get the first
implementation, and into <code>double</code> to get the second.
<p>
The full template definition allows for this formal character of the
<code>Type</code> typename. Using the keyword <code>template</code>, we prefix one line to
our initial definition, obtaining the following template function
definition:
        <pre>
    template &lt;typename Type&gt;
    Type add(Type const &amp;lvalue, Type const &amp;rvalue)
    {
        return lvalue + rvalue;
    }
</pre>
    In this definition we distinguish:
    <ul>
    <li> The keyword <code>template</code>, starting a template definition or
declaration.
    <li> The angle bracket enclosed list following <code>template</code>: it is a list,
containing one or more comma-separated elements. This angle bracket enclosed
list is called the
    <a name="an2544"></a>
<em>template parameter list</em>. When multiple elements are used, it could
look like, e.g.,
        <pre>
        typename Type1, typename Type2
</pre>
    <li> Inside the template parameter list we find the <a name="an2545"></a>
<em>formal type name</em>
<code>Type</code>. It is a formal type name, comparable to a formal parameter name in a
function's definition. Up to now we've only encountered formal variable names
with functions. The <em>types</em> of the parameters were always known by the time
the function was defined. Templates escalate the notion of formal names one
step further up the ladder, allowing type names to be formalized, rather than
just the formal parameter variable names themselves. The fact that <code>Type</code> is
a formal type name is indicated by the keyword <code>typename</code>, prefixed to
<code>Type</code> in the template parameter list. A formal type name like <code>Type</code> is
also called a <a name="an2546"></a>
<em>template type parameter</em>. Template non-type parameters also
exist, and are introduced below.
<p>
Other texts on <strong>C++</strong> sometimes use the keyword <a name="an2547"></a>
<code>class</code> where we use
<a name="an2548"></a>
 <code>typename</code>. So, in other texts
template definitions might start with a line like:
        <pre>
        template &lt;class Type&gt;
</pre>
    Using <code>class</code> instead of <code>typename</code> is now, however, considered an
<a name="an2549"></a>
anachronism, and is <a name="an2550"></a>
deprecated: a template type parameter is, after all,
a type name.
    <li> The function head: it is like a normal function head, albeit that the
template's type parameters must be used in its parameter list. When the
function is actually called, using actual arguments having actual types, these
actual types are then used by the compiler to determine which
version (overloaded to fit the actual argument types) of the template function
must be used. At this point (i.e., where the function is called), the compiler
will create the concrete function, a process called <a name="an2551"></a>
<em>instantiation</em>. The
function head may also use a formal type to specify its return value. This
feature was actually used in the <code>add()</code> template's definition.
    <li> The function parameters are specified as <code>Type const &amp;</code>
parameters. This has the usual meaning: the parameters are references to
<code>Type</code> objects or values that will not be modified by the function.
    <li> The function body: it is like a normal function body. In the body the
formal type names may be used to define or declare variables, which may then
be used as any other local variable. Even so, there are some
restrictions. Looking at <code>add()</code>'s body, it is clear that <code>operator+()</code> is
used, as well as a copy constructor, as the function returns a value. This
allows us to formulate the following restrictions for the formal type
<code>Type</code>:
        <ul>
        <li> <code>Type</code> should support <code>operator+()</code>
        <li> <code>Type</code> should support a copy constructor
        </ul>
    Consequently, while <code>Type</code> could be a <code>std::string</code>, it could never be
an <code>ostream</code>, as neither <code>operator+()</code> nor the copy constructor are
available for streams.
    </ul>
    Normal <a name="an2552"></a>
scope rules and <a name="an2553"></a>
identifier visibility rules apply to template
definitions. Formal typenames overrule, within the template definition's
scope, any identifiers having identical names having wider scopes.
<p>
Look again at the function's parameters, as defined in its parameter list.  By
specifying <code>Type const &amp;</code> rather than <code>Type</code> superfluous copying is
prevented, at the same time allowing values of primitive types to be passed as
arguments to the function. So, when <code>add(3, 4)</code> is called, <code>int(4)</code> will
be assigned to <code>Type const &amp;rvalue</code>. In general, function parameters should
be defined as <code>Type const &amp;</code> to prevent unnecessary copying. The compiler is
smart enough to handle `references to references' in this case, which is
something the language normally does not supports. For example, consider the
following <code>main()</code> function (here and in the following simple examples
assuming the template and required headers and namespace declarations have
been provided):
        <pre>
    int main()
    {
        size_t const &amp;uc = size_t(4);
        cout &lt;&lt; add(uc, uc) &lt;&lt; endl;
    }
</pre>
    Here <code>uc</code> is a reference to a constant <code>size_t</code>. It is passed as
argument to <code>add()</code>, thereby initializing <code>lvalue</code> and <code>rvalue</code> as
<code>Type const &amp;</code> to <code>size_t const &amp;</code> values, with the compiler
interpreting <code>Type</code> as <code>size_t</code>. Alternatively, the parameters might
have been specified using <code>Type &amp;</code>, rather than <code>Type const &amp;</code>. The
disadvantage of this (non-const) specification being that temporary values
cannot be passed to the function anymore. The following will fail to compile:
        <pre>
    int main()
    {
        cout &lt;&lt; add(string("a"), string("b")) &lt;&lt; endl;
    }
</pre>
    Here, a <code>string const &amp;</code> cannot be used to initialize a <code>string &amp;</code>. On
the other hand, the following <em>will</em> compile, with the compiler deciding
that <code>Type</code> should be considered a <code>string const</code>:
        <pre>
    int main()
    {
        string const &amp;s = string("a");
        cout &lt;&lt; add(s, s) &lt;&lt; endl;
    }
</pre>
    What can we deduce from these examples?
    <ul>
    <li> In general, function parameters should be specified as <code>Type const
&amp;</code> parameters to prevent unnecessary copying.
    <li> The template mechanism is fairly flexible, in that it will interpret
formal types as plain types, const types, pointer types, etc., depending on
the actually provided types. The <a name="an2554"></a>
rule of thumb is that the formal type is
used as a generic mask for the actual type, with the formal type name covering
whatever part of the actual type must be covered. Some examples, assuming the
parameter is defined as <code>Type const &amp;</code>:
            <center>
        <table>

        
<tr>

            <td> <strong>argument type</strong></td> <td> <strong>Type ==</strong></td>

         
</tr>

        
<tr>

            <td> <code>size_t const</code></td> <td> <code>size_t</code></td>

         
</tr>

        
<tr>

            <td> <code>size_t</code></td> <td> <code>size_t</code></td>

         
</tr>

        
<tr>

            <td> <code>size_t *</code></td> <td> <code>size_t *</code></td>

         
</tr>

        
<tr>

            <td> <code>size_t const *</code></td> <td> <code>size_t const *</code></td>

         
</tr>

        
</table>
            </center>
    </ul>
    As a second example of a template function, consider the following
function definition:
        <pre>
    template &lt;typename Type, size_t Size&gt;
    Type sum(Type const (&amp;array)[Size])
    {
        Type t = Type();

        for (size_t idx = 0; idx &lt; Size; idx++)
            t += array[idx];

        return t;
    }
</pre>
    This template definition introduces the following new concepts and
features:
    <ul>
    <li> Its template parameter list has two elements. Its first element is a
well-known template type parameter, but its second element has a very specific
type: an <code>size_t</code>. Template parameters of specific (i.e., non-formal)
types used in template parameter lists are called
    <a name="an2555"></a>
<em>template non-type parameters</em>.
    A template <a name="an2556"></a>
<em>non-type parameter</em> represents a <a name="an2557"></a>
constant expression,
which must be known by the time the template is instantiated, and which is
specified in terms of existing types, such as an <code>size_t</code>.
    <li> Looking at the function's head, we see one parameter:
        <pre>
        Type const (&amp;array)[Size]
</pre>
    This parameter defines <code>array</code> as a reference parameter to an
array having <code>Size</code> elements of type <code>Type</code>, that may not be modified.
    <li> In the parameter definition, both <code>Type</code> and <code>Size</code> are
used. <code>Type</code> is of course the template's type parameter <code>Type</code>, but
<code>Size</code> is also a template parameter. It is an <code>size_t</code>, whose value must
be inferable by the compiler when it compiles an actual call of the  <code>sum()</code>
template function. Consequently, <code>Size</code> must be a <code>const</code> value. Such a
constant expression is called a <a name="an2558"></a>
<em>template non-type parameter</em>, and it is
named in the template's parameter list.
    <li> When the template function is called, the compiler must be able to
infer not only <code>Type</code>'s concrete value, but also <code>Size</code>'s value. Since
the function <code>sum()</code> only has one parameter, the compiler is only able to
infer <code>Size</code>'s value from the function's actual argument. It can do so if
the provided argument is an array (of known and fixed size), rather
than a pointer to <code>Type</code> elements. So, in the following <code>main()</code> function
the first statement will compile correctly, whereas the second statement
won't:
        <pre>
    int main()
    {
        int values[5];
        int *ip = values;

        cout &lt;&lt; sum(values) &lt;&lt; endl;    // compiles ok
        cout &lt;&lt; sum(ip) &lt;&lt; endl;        // won't compile
    }
</pre>
    <li> Inside the function, the statement <code>Type t = Type()</code> is used to
initialize <code>t</code> to a default value. Note here that no fixed value (like 0) is
used. Any type's default value may be obtained using its default constructor,
        <a name="an2559"></a>

    rather than using a fixed numerical value. Of course, not every class
accepts a numerical value as an argument to one of its constructors. But all
types, even the primitive types, support default constructors (actually, some
classes do not implement a default constructor, but most do). The default
constructor of primitive types will initialize their variables to 0 (or
<code>false</code>). Furthermore, the statement <code>Type t = Type()</code> is a true
initialization: <code>t</code> is initialized by <code>Type</code>'s default constructor, rather
than using <code>Type</code>'s copy constructor to assign <code>Type()</code>'s copy to
<code>t</code>. Alternatively, the syntactical construction <code>Type t(Type())</code> could
have been used.
<p>
<li> Comparable to the first template function, <code>sum()</code> also assumes the
existence of certain public members in <code>Type</code>'s class. This time
<code>operator+=()</code> and <code>Type</code>'s copy constructor.
    </ul>
<p>
Like class definitions, template definitions should not contain <code>using</code>
        <a name="an2560"></a>

        <a name="an2561"></a>

    directives or declarations: the template might be used in a situation
where such a directive overrides the programmer's intentions: ambiguities or
other conflicts may result from the template's author and the programmer using
different <code>using</code> directives (E.g, a <code>cout</code> variable defined in the
<code>std</code> namespace and in the programmer's own namespace). Instead, within
template definitions only fully qualified names, including all required
namespace specifications should be used.
<p>
<a name="TEMPFUNARGS"></a><a name="l322"></a>
<h2>18.2: Argument deduction</h2>
<a name="templatefunctions/argumentdeduction"></a>    In this section we'll concentrate on the process by which the compiler
deduces the actual types of the template type parameters when a template
function is called, a process called <a name="an2562"></a>
<em>template parameter deduction</em>. As
we've already seen, the compiler is able to substitute a wide range of actual
types for a single formal template type parameter. Even so, not every
thinkable conversion is possible. In particular when a function has multiple
parameters of the same template type parameter, the compiler is very
restrictive in what argument types  it will actually accept.
<p>
When the compiler deduces the actual types for template type parameters,
it will only consider the types of the arguments. Neither local variables nor
the function's return value is considered in this process. This is
understandable: when a function is called, the compiler will only see the
template function's arguments with certainty. At the point of the call it will
definitely not see the types of the function's local variables, and the
function's return value might not actually be used, or may be assigned to a
variable of a subrange (or super-range) type of a deduced template type
parameter. So, in the following example, the compiler won't ever be able to
call <code>fun()</code>, as it has no way to deduce the actual type for the <code>Type</code>
template type parameter.
        <pre>
    template &lt;typename Type&gt;
    Type fun()              // can never be called
    {
        return Type();
    }
</pre>
    In general, when a function has multiple parameters of identical template
type parameters, the actual types must be exactly the same. So, whereas
        <pre>
        void binarg(double x, double y);
</pre>
    may be called using an <code>int</code> and a <code>double</code>, with the <code>int</code> argument
implicitly being converted to a <code>double</code>, the corresponding
template function cannot be called using an <code>int</code> and <code>double</code> argument:
the compiler won't itself promote <code>int</code> to <code>double</code> and to decide next
that <code>Type</code> should be <code>double</code>:
        <pre>
    template &lt;typename Type&gt;
    void binarg(Type const &amp;p1, Type const &amp;p2)
    {}

    int main()
    {
        binarg(4, 4.5); // ?? won't compile: different actual types
    }
</pre>
<p>
What, then, are the transformations the compiler will apply when deducing
the actual types of template type parameters? It will perform only three types
of
        <a name="an2563"></a>

    parameter type transformations (and a fourth one to function parameters of
any fixed type (i.e., of a non-template function parameter type)). If it
cannot deduce the actual types using these transformations, the template
function will not be considered. These transformations are:
    <ul>
    <li> <em>lvalue transformations</em>, creating an <em>rvalue</em> from an
<em>lvalue</em>;
    <li> <em>qualification transformations</em>, inserting a <code>const</code> modifier to
a non-constant argument type;
    <li> <em>transformation to a base class instantiated from a class template</em>,
using a template base class when an argument of a template derived class type
was provided in the call.
    <li> Standard transformations for template non-type function
parameters. This isn't a template parameter type transformation, but it refers
to any remaining template non-type parameter of template functions. For these
function parameters the compiler will perform any standard conversion it has
available (e.g., <code>int</code> to <code>size_t</code>, <code>int</code> to <code>double</code>, etc.).
    </ul>
    The first three types of transformations will now be discussed and
illustrated.
<p>
<a name="l323"></a>
<h3>18.2.1: Lvalue transformations</h3>
    <a name="templatefunctions/lvalue"></a>There are three types of <a name="an2564"></a>
<em>lvalue transformations</em>:
    <ul>
    <li> <strong>lvalue-to-rvalue transformations.</strong>
        <blockquote>An <a name="an2565"></a>
lvalue-to-rvalue transformation is applied when an <code>rvalue</code>
is required, and an <code>lvalue</code> is used as argument.  This happens when a
variable is used as argument to a function specifying a
    <a name="an2566"></a>
<em>value parameter</em>. For example,
        <pre>
    template&lt;typename Type&gt;
    Type negate(Type value)
    {
        return -value;
    }
    int main()
    {
        int x = 5;
        x = negate(x);  // lvalue (x) to rvalue (copies x)
    }
</pre>
    </blockquote>
    <li> <strong>array-to-pointer transformations.</strong>
        <blockquote>An <a name="an2567"></a>
array-to-pointer transformation
is applied when the name of an array is assigned to a pointer variable. This
is frequently seen with functions defining pointer parameters. When calling
such functions, arrays are often specified as their arguments. The
array's address is then assigned to the pointer-parameter, and its type is
used to deduce the corresponding template parameter's type. For example:
        <pre>
    template&lt;typename Type&gt;
    Type sum(Type *tp, size_t n)
    {
        return accumulate(tp, tp + n, Type());
    }
    int main()
    {
        int x[10];
        sum(x, 10);
    }
</pre>
    In this example, the location of the array <code>x</code> is passed to <code>sum()</code>,
expecting a pointer to some type. Using the array-to-pointer transformation,
<code>x</code>'s address is considered a pointer value which is assigned to <code>tp</code>,
deducing that <code>Type</code> is <code>int</code> in the process.
    </blockquote>
    <li> <strong>function-to-pointer transformations.</strong>
        <blockquote>This transformation is most often seen with template functions
defining a parameter which is a pointer to a function. When calling such a
function the name of a function may be specified as its argument. The address
of the function is then assigned to the pointer-parameter, deducing the
template type parameter in the process. This is called a
    <a name="an2568"></a>
function-to-pointer transformation. For example:
        <pre>
    #include &lt;cmath&gt;

    template&lt;typename Type&gt;
    void call(Type (*fp)(Type), Type const &amp;value)
    {
        (*fp)(value);
    }
    int main()
    {
        call(&amp;sqrt, 2.0);
    }
</pre>
    In this example, the address of the <code>sqrt()</code> function is passed to
<code>call()</code>, expecting a pointer to a function returning a <code>Type</code> and
expecting a <code>Type</code> for its argument. Using the function-to-pointer
transformation, <code>sqrt</code>'s address is considered a pointer value which is assigned
to <code>fp</code>, deducing that <code>Type</code> is <code>double</code> in the process. Note that the
argument <code>2.0</code> could not have been specified as <code>2</code>, as there is no <code>int
sqrt(int)</code> prototype. Also note that the function's first parameter specifies
<code>Type (*fp)(Type)</code>, rather than <code>Type (*fp)(Type const &amp;)</code> as might have
been expected from our previous discussion about how to specify the types of
template function's parameters, preferring references over values.
However, <code>fp</code>'s argument <code>Type</code> is not a template function parameter, but
a parameter of the function <code>fp</code> points to. Since <code>sqrt()</code> has prototype
<code>double sqrt(double)</code>, rather than <code>double sqrt(double const &amp;)</code>,
<code>call()</code>'s parameter <code>fp</code> <em>must</em> be specified as <code>Type
(*fp)(Type)</code>. It's that strict.
    </blockquote>
    </ul>
<p>
<a name="l324"></a>
<h3>18.2.2: Qualification transformations</h3>
    <a name="templatefunctions/qualifications"></a>A <a name="an2569"></a>
<em>qualification transformation</em> adds <a name="an2570"></a>
<code>const</code> or <a name="an2571"></a>
<code>volatile</code> qualifications
to <em>pointers</em>. This transformation is applied when the template function's
parameter is explicitly defined using a <code>const</code> (or <code>volatile</code>) modifier,
and the function's argument isn't a <code>const</code> or <code>volatile</code> entity. In that
case, the transformation adds <code>const</code> or <code>volatile</code>, and subsequently deduces
the template's type parameter. For example:
        <pre>
    template&lt;typename Type&gt;
    Type negate(Type const &amp;value)
    {
        return -value;
    }
    int main()
    {
        int x = 5;
        x = negate(x);
    }
</pre>
    Here we see the template function's <code>Type const &amp;value</code> parameter: a
reference to a <code>const Type</code>. However, the argument isn't a <code>const int</code>,
but an <code>int</code> that can be modified. Applying a qualification transformation, the
compiler adds <code>const</code> to <code>x</code>'s type, and so it matches <code>int const x</code>
with <code>Type const &amp;value</code>, deducing that <code>Type</code> must be <code>int</code>.
<p>
<a name="l325"></a>
<h3>18.2.3: Transformation to a base class</h3>
    <a name="templatefunctions/baseclass"></a>Although the <em>construction</em> of template classes will only be constructed in
chapter <a href="cplusplus19.html#TEMPCLASS">19</a>, template classes have already extensively been
<em>used</em> earlier. For example, abstract containers (covered in chapter
<a href="cplusplus12.html#Containers">12</a>) are actually defined as template classes.  Like
        <a name="an2572"></a>

    concrete classes (i.e., non-template classes), template classes can
participate in the construction of
        <a name="an2573"></a>
class hierarchies.
    In section <a href="cplusplus19.html#DERIVEDTEMPCLASS">19.9</a> it is shown how a <a name="an2574"></a>
template class can
be derived from another template class.
<p>
As template class derivation remains to be covered, the following
discussion is necessarily somewhat abstract. Optionally, the reader may of
course skip briefly to section <a href="cplusplus19.html#DERIVEDTEMPCLASS">19.9</a>, to read this
section thereafter.
<p>
In this section it should now be assumed, for the sake of argument, that a
template class <code>Vector</code> has somehow been derived from a <code>std::vector</code>.
Furthermore, assume that the following template function has been
constructed to sort a vector using some function object <code>obj</code>:
        <pre>
    template &lt;typename Type, typename Object&gt;
    void sortVector(std::vector&lt;Type&gt; vect, Object const &amp;obj)
    {
        sort(vect.begin(), vect.end(), obj);
    }
</pre>
    To sort <code>std::vector&lt;string&gt;</code> objects case-insensitively, the <code>class
Caseless</code> could be constructed as follows:
        <pre>
    class CaseLess
    {
        public:
            bool operator()(std::string const &amp;before,
                            std::string const &amp;after) const
            {
                return strcasecmp(before.c_str(), after.c_str()) &lt; 0;
            }
    };
</pre>
    Now various vectors may be sorted, using <code>sortVector()</code>:
        <pre>
    int main()
    {
        std::vector&lt;string&gt; vs;
        std::vector&lt;int&gt; vi;

        sortVector(vs, CaseLess());
        sortVector(vi, less&lt;int&gt;());
    }
</pre>
    Applying the transformation
        <a name="an2575"></a>

        <a name="an2576"></a>

    <em>transformation to a base class instantiated from a class template</em>, the
template function <code>sortVectors()</code> may now also be used to sort <code>Vector</code>
objects. For example:
        <pre>
    int main()
    {
        Vector&lt;string&gt; vs;      // note: not `std::vector'
        Vector&lt;int&gt; vi;

        sortVector(vs, CaseLess());
        sortVector(vi, less&lt;int&gt;());
    }
</pre>
    In this example, <code>Vector</code>s were passed as argument to
<code>sortVector()</code>. Applying the transformation to a base class instantiated
from a class template, the compiler will consider <code>Vector</code> to be a
<code>std::vector</code>, and is thus able to deduce the template's type parameter. A
<code>std::string</code> for the <code>Vector vs</code>, an <code>int</code> for <code>Vector vi</code>.
<p>
Please realize the purpose of the various template parameter type deduction
transformations. They do not aim at matching function arguments to function
parameters, but having matched arguments to parameters, the transformations
may be applied to determine the actual types of the various template type
parameters.
<p>
<a name="PARDEDUCT"></a><a name="l326"></a>
<h3>18.2.4: The template parameter deduction algorithm</h3>
    <a name="templatefunctions/algorithm"></a>    The compiler uses the following <a name="an2577"></a>
algorithm to deduce the actual types of
        <a name="an2578"></a>

its template type parameters:
    <ul>
    <li> In turn, the template function's parameters are identified using the
arguments of the called function.
    <li> For each template parameter used in the template function's parameter
list, the template type parameter is matched with the corresponding argument's
type (e.g., <code>Type</code> is <code>int</code> if the argument is <code>int x</code>, and the
function's parameter is <code>Type &amp;value</code>).
    <li> While matching the argument types to the template type parameters,
the three allowed transformations (see section <a href="cplusplus18.html#TEMPFUNARGS">18.2</a>) for template
type parameters are applied where necessary.
    <li> If identical template type parameters
        <a name="an2579"></a>

    are used with multiple function parameters, the deduced template types
must be exactly the same. So, the next template function cannot be called with
an <code>int</code> and a <code>double</code> argument:
        <pre>
    template &lt;typename Type&gt;
    Type add(Type const &amp;lvalue, Type const &amp;rvalue)
    {
        return lvalue + rvalue;
    }
</pre>
    When calling this template function, two identical types must be used
(albeit that the three standard transformations are of course allowed). If the
template deduction mechanism does not come up with identical actual types for
identical template types, then the template function will not be instantiated.
    </ul>
<p>
<a name="TEMPFUNDECL"></a><a name="l327"></a>
<h2>18.3: Declaring template functions</h2>
<a name="templatefunctions/declarations"></a>    Up to now, we've only defined template functions. There are various
        <a name="an2580"></a>

consequences of including template function definitions in multiple source
files, none of them serious, but worth knowing.
    <ul>
    <li> Like class interfaces, template definitions are usually included in
header files. Every time a header file containing a template definition is
read by the compiler, the compiler must process the definition in full, even
though it might not actually need the template. This will relatively slow-down
the compilation. For example, compiling a template header file like
<code>algorithm</code> on my old laptop takes about four times the amount of time it
takes to compile a plain header file like <code>cmath</code>. The header file
<code>iostream</code> is even harder to process, requiring almost 15 times the amount
of time it takes to process <code>cmath</code>. Clearly, processing templates is
serious business for the compiler.
    <li> Every time a template function is instantiated, its code appears in
the resulting object module. However, if multiple instantiations of a
template, using the same actual types for its template parameter exist in
multiple object files, then the linker will weed out superfluous
instantiations. In the final program only one instantiation for a particular
set of actual template type parameters will be used (see also section
<a href="cplusplus18.html#TEMPFUNINST">18.4</a> for an illustration). Therefore, the linker will have an
additional task to perform (<em>viz.</em> weeding out multiple instantiations),
which will slow down the linking process.
    <li> Sometimes the definitions themselves are not required, but only
references or pointers to the templates are required. Requiring the compiler
to process the full template definitions in those cases will unnecessarily
slow down the compilation process.
    </ul>
    Instead of including template definitions again and again in various
source files, templates may also be declared. When templates are declared, the
compiler will not have to process the template's definitions again and again,
and no instantiations will be created on the basis of template declarations
alone. Any actually required instantiation must, as holding true for
declarations in general, be available elsewhere. Unlike the situation we
encounter with concrete functions, which are usually stored in libraries, it
is currently not possible to store templates in libraries (although
precompiled header files may be implemented in various
compilers). Consequently, using template declarations puts a burden on the
shoulders of the software engineer, who has to make sure that the required
instantiations exist. Below a simple way to accomplish that is introduced.
<p>
A template function declaration is simply created: the function's body is
replaced by a semicolon. Note that this is exactly identical to the way
concrete function declarations are constructed. So, the previously defined
template function <code>add()</code> can simply be declared as
        <pre>
    template &lt;typename Type&gt;
    Type add(Type const &amp;lvalue, Type const &amp;rvalue);
</pre>
<p>
Actually, we've already encountered <a name="an2581"></a>
template declarations. The header
file <code>iosfwd</code> may be included in sources not requiring instantiations
        <a name="an2582"></a>

    of elements from the class <a name="an2583"></a>
<code>ios</code> and its derived classes. For example,
in order to compile the <em>declaration</em>
        <pre>
        std::string getCsvline(std::istream &amp;in, char const *delim);
</pre>
    it is not necessary to include the <code>string</code> and <code>istream</code> header
files. Rather, a single
        <pre>
        #include &lt;iosfwd&gt;
</pre>
    is sufficient, requiring about one-ninth the amount of time it takes to
compile the declaration when <code>string</code> and <code>istream</code> are included.
<p>
<a name="TEMPFUNEXDEC"></a><a name="l328"></a>
<h3>18.3.1: Instantiation declarations</h3>
    <a name="templatefunctions/instantdecl"></a>    So, if declaring template functions speeds up the compilation and the
linking phases of a program, how can we make sure that the required
instantiations of the template functions will be available when the program is
eventually linked together?
<p>
For this a variant of a declaration is available, a so-called
        <a name="an2584"></a>
<em>explicit instantiation declaration</em>.
    An explicit instantiation declaration contains the following elements:
    <ul>
    <li> It starts with the keyword <a name="an2585"></a>
<code>template</code>, omitting the template
parameter list.
    <li> Next the function's return type and name are specified.
    <li> The function name is followed by a <a name="an2586"></a>
<em>type specification list</em>, a
list of types between angle brackets, each type specifying the actual type
of the corresponding template type parameter in the template's parameter list.
    <li> Finally the function's parameter list is specified, terminated by a
semicolon.
    </ul>
    Although this is a <a name="an2587"></a>
declaration, it is actually understood by the
compiler as a request to instantiate that particular variant of the function.
<p>
Using explicit instantiation declarations all instantiations of template
functions required by a program can be collected in one file. This file, which
should be a normal <em>source</em> file, should include the template definition
header file, and should next specify the required instantiation
declarations. Since it's a source file, it will not be included by other
sources. So namespace <code>using</code> directives and declarations
        <a name="an2588"></a>

    may safely be used once the required headers have been included.  Here is
an example showing the required instantiations for our earlier <code>add()</code>
template, instantiated for <code>double</code>, <code>int</code>, and <code>std::string</code> types:
        <pre>
    #include "add.h"
    #include &lt;string&gt;
    using namespace std;

    template int add&lt;int&gt;(int const &amp;lvalue, int const &amp;rvalue);
    template double add&lt;double&gt;(double const &amp;lvalue, double const &amp;rvalue);
    template string add&lt;string&gt;(string const &amp;lvalue, string const &amp;rvalue);
</pre>
    If we're sloppy and forget to mention an instantiation required by our
program, then the repair can easily be made: just add the missing instantiation
declaration to the above list. After recompiling the file and relinking the
program we're done.
<p>
<a name="TEMPFUNINST"></a><a name="l329"></a>
<h2>18.4: Instantiating template functions</h2>
<a name="templatefunctions/instantiations"></a>    A template is not instantiated when its definition is read by the
compiler. A template is merely a <em>recipe</em> telling the compiler how to create
particular code once it's time to do so. It's very much like a recipe in a
cooking book: you reading a cake's recipe doesn't mean you have actually
cooked that cake by the time you've read the recipe.
<p>
So, when is a template function actually instantiated? There are two
situations in which the compiler will decide to  instantiate templates:
    <ul>
    <li> They are instantiated when they're actually used (e.g., the function
<code>add()</code> is called with a pair of <code>size_t</code> values);
    <li> When addresses of template functions are taken they are instantiated.
For example:
        <pre>
    #include "add.h"

    char (*addptr)(char const &amp;, char const &amp;) = add;
</pre>
    </ul>
    The location of statements causing the compiler to instantiate a template
is called the template's
        <a name="an2589"></a>

    <a name="an2590"></a>
<em>point of instantiation</em>. The point of instantiation has serious
implications for the template function's code. These implications are
discussed in section <a href="cplusplus18.html#NAMERESFUN">18.9</a>.
<p>
The compiler is not always able to deduce the template's type parameters
unambiguously. In that case the compiler reports an ambiguity which must be
solved by the software engineer. Consider the following code:
        <pre>
    #include &lt;iostream&gt;
    #include "add.h"

    size_t fun(int (*f)(int *p, size_t n));
    double fun(double (*f)(double *p, size_t n));

    int main()
    {
        std::cout &lt;&lt; fun(add) &lt;&lt; std::endl;
    }
</pre>
    When this small program is compiled, the compiler reports an ambiguity it
cannot resolve. It has two candidate functions, as for each overloaded version
of <code>fun()</code> a proper instantiation of <code>add()</code> can be constructed:
        <pre>
    error: call of overloaded 'fun(&lt;unknown type&gt;)' is ambiguous
    note: candidates are: int fun(size_t (*)(int*, size_t))
    note:                 double fun(double (*)(double*, size_t))
</pre>
    Situations like these should of course be avoided. Template functions can
only be instantiated if there's no ambiguity. Ambiguities arise when multiple
functions emerge from the compiler's function selection mechanism (see section
<a href="cplusplus18.html#FUNCTIONSELECTION">18.8</a>). It is up to us to resolve these
ambiguities. Ambiguities like the above can be resolved using a blunt
<a name="an2591"></a>
<code>static_cast</code> (as we select among alternatives, all of them possible and
available):
        <pre>
    #include &lt;iostream&gt;
    #include "add.h"

    int fun(int (*f)(int const &amp;lvalue, int const &amp;rvalue));
    double fun(double (*f)(double const &amp;lvalue, double const &amp;rvalue));

    int main()
    {
        std::cout &lt;&lt; fun(
                        static_cast&lt;int (*)(int const &amp;, int const &amp;)&gt;(add)
                    ) &lt;&lt; std::endl;
        return 0;
    }
</pre>
    But if possible, type casts should be avoided. How to avoid casts in
situations like these is explained in the next section (<a href="cplusplus18.html#TEMPFUNEXPLICIT">18.5</a>).
<p>
As mentioned in section <a href="cplusplus18.html#TEMPFUNDECL">18.3</a>, the linker will remove
        <a name="an2592"></a>

identical instantiations of a template from the final program,
leaving only one instantiation for each unique set of actual template type
parameters. Let's have a look at an example showing this behavior of the
linker. To illustrate the linker's behavior, we will do as follows:
    <ul>
    <li> First we construct several source files:
            <ul>
            <li><code>source1.cc</code> defines a function <code>fun()</code>, instantiating
<code>add()</code> for <code>int</code>-type arguments, including <code>add()</code>'s template
definition. It displays <code>add()</code>'s address. Here is <code>source1.cc</code>:
        <pre>
    union PointerUnion
    {
        int (*fp)(int const &amp;, int const &amp;);
        void *vp;
    };
</pre>
        <pre>
    #include &lt;iostream&gt;
    #include "add.h"
    #include "pointerunion.h"

    void fun()
    {
        PointerUnion pu = { add };

        std::cout &lt;&lt; pu.vp &lt;&lt; std::endl;
    }
</pre>
            <li><code>source2.cc</code> defines the same function, but only declares the
proper <code>add()</code> template, using a template declaration (<em>not</em> an
instantiation declaration). Here is <code>source2.cc</code>:
        <pre>
    #include &lt;iostream&gt;
    #include "pointerunion.h"

    template&lt;typename Type&gt;
    Type add(Type const &amp;, Type const &amp;);

    void fun()
    {
        PointerUnion pu = { add };

        std::cout &lt;&lt; pu.vp &lt;&lt; std::endl;
    }
</pre>
            <li><code>main.cc</code> again includes <code>add()</code>'s template definition,
declares the function <code>fun()</code> and defines <code>main()</code>, defining <code>add()</code>
for <code>int</code>-type arguments as well and displaying <code>add()</code>'s function
address. It also calls the function <code>fun()</code>. Here is <code>main.cc</code>:
        <pre>
    #include &lt;iostream&gt;
    #include "add.h"
    #include "pointerunion.h"

    void fun();

    int main()
    {
        PointerUnion pu = { add };

        fun();
        std::cout &lt;&lt; pu.vp &lt;&lt; std::endl;
    }
</pre>
            </ul>
    <li> All sources are compiled to object modules. Note the different sizes
of <code>source1.o</code> (2112 bytes, using <code>g++</code> version 4.0.4. All sizes reported
here may differ somewhat for different compilers and/or run-time libraries)
and <code>source2.o</code> (1928 bytes). Since <code>source1.o</code> contains the instantiation
of <code>add()</code>, it is somewhat larger than <code>source2.o</code>, containing only the
template's declaration. Now we're ready to start our little experiment.
    <li> Linking <code>main.o</code> and <code>source1.o</code>, we obviously link together two
object modules, each containing its own instantiation of the same template
function. The resulting program produces the following output:
        <pre>
    0x80486d8
    0x80486d8
</pre>
        Furthermore, the size of the resulting program is 9152 bytes.
    <li> Linking <code>main.o</code> and <code>source2.o</code>, we now link together an object
module containing the instantiation of the <code>add()</code> template, and another
object module containing the mere declaration of the same template
function. So, the resulting program cannot but contain a single instantiation
of the required template function. This program has exactly the same size, and
produces exactly the same output as the first program.
    </ul>
    So, from our little experiment we can conclude that the linker will indeed
remove identical template instantiations from a final program, and that using
mere template declarations will not result in template instantiations.
<p>
<a name="TEMPFUNEXPLICIT"></a><a name="l330"></a>
<h2>18.5: Using explicit template types</h2>
<a name="templatefunctions/explicit"></a>    In the previous section (section <a href="cplusplus18.html#TEMPFUNINST">18.4</a>) we've seen that the
compiler may encounter ambiguities when attempting to instantiate a
template. We've seen an example in which overloaded versions of a function
<code>fun()</code> existed, expecting different types of arguments, both of which
could have been provided by an instantiation of a template function. The
intuitive way to solve such an ambiguity is to use a <code>static_cast</code> type
cast, but as noted: if possible, casts should be avoided.
<p>
When template functions are involved, such a <code>static_cast</code> may indeed
neatly be avoided, using <a name="an2593"></a>
<em>explicit template type arguments</em>. When
explicit template type arguments are used the compiler is explicitly
informed about the actual template type parameters it should use when
instantiating a template. Here, the function's name is followed by an
        <a name="an2594"></a>
<em>actual template parameter type list</em>
        <a name="an2595"></a>

    which may again be followed by the function's argument list, if
required. The actual types mentioned in the actual template parameter list
are used by the compiler to `deduce' the actual types of the corresponding
template types of the function's template parameter type list. Here is the
same example as given in the previous section, now using  explicit template
type arguments:
        <pre>
    #include &lt;iostream&gt;
    #include "add.h"

    int fun(int (*f)(int const &amp;lvalue, int const &amp;rvalue));
    double fun(double (*f)(double const &amp;lvalue, double const &amp;rvalue));

    int main()
    {
        std::cout &lt;&lt; fun(add&lt;int&gt;) &lt;&lt; std::endl;
        return 0;
    }
</pre>
<p>
<a name="l331"></a>
<h2>18.6: Overloading template functions</h2>
<a name="templatefunctions/overloading"></a>    Let's once again look at our <code>add()</code> template. That template was
designed to return the sum of two entities. If we would want to compute the
sum of three entities, we could write:
        <pre>
    int main()
    {
        add(2, add(3, 4));
    }
</pre>
    This is a perfectly acceptable solution for the occasional
situation. However, if we would have to add three entities regularly, an
<em>overloaded</em> version of the <code>add()</code> function, expecting three arguments,
might be a useful thing to have. The solution for this problems is simple:
template functions may be overloaded.
        <a name="an2596"></a>

<p>
To define an overloaded version, merely put multiple definitions of the
template in its definition header file. So, with the <code>add()</code> function this
would be something like:
        <pre>
    template &lt;typename Type&gt;
    Type add(Type const &amp;lvalue, Type const &amp;rvalue)
    {
        return lvalue + rvalue;
    }

    template &lt;typename Type&gt;
    Type add(Type const &amp;lvalue, Type const &amp;mvalue, Type const &amp;rvalue)
    {
        return lvalue + mvalue + rvalue;
    }
</pre>
    The overloaded function does not have to be defined in terms of simple
values. Like all overloaded functions, just a unique set of function
parameters is enough to define an overloaded version. For example, here's an
overloaded version that can be used to compute the sum of the elements of a
vector:
        <pre>
    template &lt;typename Type&gt;
    Type add(std::vector&lt;Type&gt; const &amp;vect)
    {
        return accumulate(vect.begin(), vect.end(), Type());
    }
</pre>
<p>
Overloading templates does not have to restrict itself to the function's
parameter list. The template's type parameter list itself may also be
    <a name="an2597"></a>

overloaded. The last definition of the <code>add()</code> template allows us to specify
a <code>std::vector</code> as its first argument, but no <code>deque</code> or
<code>map</code>. Overloaded versions for those types of containers could of course be
constructed, but where's the end to that? Instead, let's look for common
characteristics of these containers, and if found, define an overloaded
template function on these common characteristics. One common characteristic
of the mentioned containers is that they all support <code>begin()</code> and <code>end()</code>
members, returning iterators. Using this, we could define a template type
parameter representing containers that must support these members. But
mentioning a plain `container type' doesn't tell us for what data type it has
been instantiated. So we need a second template type parameter representing
the container's data type, thus overloading the template's type parameter
list. Here is the resulting overloaded version of the <code>add()</code> template:
        <pre>
    template &lt;typename Container, typename Type&gt;
    Type add(Container const &amp;cont, Type const &amp;init)
    {
        return std::accumulate(cont.begin(), cont.end(), init);
    }
</pre>
    With all these overloaded versions in place, we may now start the compiler
to compile the following function:
        <pre>
    using namespace std;

    int main()
    {
        vector&lt;int&gt; v;

        add(3, 4);          // 1 (see text)
        add(v);             // 2
        add(v, 0);          // 3
    }
</pre>
    <ul>
    <li> With the first statement, the compiler recognizes two identical
types, both <code>int</code>. It will therefore instantiate <code>add&lt;int&gt;()</code>, our very
first definition of the <code>add()</code> template.
    <li> With statement two, a single argument is used. Consequently, the
compiler will look for an overloaded version of <code>add()</code> requiring but one
argument. It finds the version expecting a <code>std::vector</code>, deducing that the
template's type parameter must be <code>int</code>. It instantiates
        <pre>
    add&lt;int&gt;(std::vector&lt;int&gt; const &amp;)
</pre>
    <li> With statement three, the compiler again encounters an argument list
holding two arguments. However, the types of the arguments are different, so
it cannot use the <code>add()</code> template's first definition. But it <em>can</em> use
the last definition, expecting entities having different types. As a
<code>std::vector</code> supports <code>begin()</code> and <code>end()</code>, the compiler is now able
to instantiate the template function
        <pre>
    add&lt;std::vector&lt;int&gt;, int&gt;(std::vector&lt;int&gt; const &amp;, int const &amp;)
</pre>
    </ul>
<p>
Having defined <code>add()</code> using two different template type parameters, and
a template function having a parameter list containing two parameters of these
types, we've exhausted the possibilities to define an <code>add()</code> function
template having a function parameter list showing two different types. Even
though the parameter types are different, we're still able to define a
template function <code>add()</code> as a template function merely returning the sum of
two differently typed entities:
        <pre>
    template &lt;typename T1, typename T2&gt;
    T1 add(T1 const &amp;lvalue, T2 const &amp;rvalue)
    {
        return lvalue + rvalue;
    }
</pre>
    However, now we won't be able to instantiate <code>add()</code> using two
differently typed arguments anymore: the compiler won't be able resolve the
ambiguity. It cannot choose which of the two overloaded versions defining two
differently typed function parameters to use:
        <pre>
    int main()
    {
        add(3, 4.5);
    }
    /*
        Compiler reports:

        error: call of overloaded `add(int, double)' is ambiguous
        error: candidates are: Type add(const Container&amp;, const Type&amp;)
                                    [with Container = int, Type = double]
        error:                 T1 add(const T1&amp;, const T2&amp;)
                                    [with T1 = int, T2 = double]
    */
</pre>
    Consider once again the overloaded function accepting three arguments:
        <pre>
    template &lt;typename Type&gt;
    Type add(Type const &amp;lvalue, Type const &amp;mvalue, Type const &amp;rvalue)
    {
        return lvalue + mvalue + rvalue;
    }
</pre>
    It may be considered as a disadvantage that only equally typed arguments
are accepted by this function: e.g., three <code>int</code>s, three <code>double</code>s or
three <code>string</code>s. To remedy this, we define yet another overloaded version of
the function, this time accepting arguments of any type. Of course, when
calling this function we must make sure that <code>operator+()</code> is defined
between them, but apart from that there appears to be no problem. Here is the
overloaded version accepting arguments of any type:
        <pre>
    template &lt;typename Type1, typename Type2, typename Type3&gt;
    Type1 add(Type1 const &amp;lvalue, Type2 const &amp;mvalue, Type3 const &amp;rvalue)
    {
        return lvalue + mvalue + rvalue;
    }
</pre>
    Now that we've defined these two overloaded versions, let's call <code>add()</code>
as follows:
        <pre>
        add(1, 2, 3);
</pre>
    In this case, one might expect the compiler to report an ambiguity. After
all, the compiler might select the former function, deducing that <code>Type ==
int</code>, but it might also select the latter function, deducing that <code>Type1 ==
int, Type2 == int</code> and <code>Type3 == int</code>. However, the compiler reports no
ambiguity. The reason for this is the following: if an overloaded template
function is defined using <em>more specialized</em> template type parameters (e.g.,
        <a name="an2598"></a>
 all equal types)
than another (overloaded) function, for which more general template type
parameters (e.g., all different) have been used, then the compiler will select
the more specialized function over the more general function wherever
possible.
<p>
As a <a name="an2599"></a>
rule of thumb: when overloaded versions of a template function
are defined, each overloaded version must use a unique combination of
template type parameters to avoid ambiguities when the templates are
instantiated. Note that the <em>ordering</em> of template type parameters in the
function's parameter list is not important. When trying to instantiate the
following <code>binarg()</code> template, an ambiguity will occur:
        <pre>
    template &lt;typename T1, typename T2&gt;
    void binarg(T1 const &amp;first, T2 const &amp;second)
    {}
    // and:
    template &lt;typename T1, typename T2&gt;
    void binarg(T2 const &amp;first, T1 const &amp;second)  // exchange T1 and T2
    {}
</pre>
    The ambiguity should come as no surprise. After all, template type
parameters are just formal names. Their names (<code>T1</code>, <code>T2</code> or <code>Whatever</code>)
have no concrete meanings whatsoever.
<p>
Finally, overloaded functions may be declared, either using plain
declarations or instantiation declarations, and explicit template parameter
types may also be used. For example:
    <ul>
    <li> Declaring a template function <code>add()</code> accepting containers
of a certain type:
        <pre>
    template &lt;typename Container, typename Type&gt;
    Type add(Container const &amp;container, Type const &amp;init);
</pre>
    <li> The same function, but now using an instantiation declaration (note
that this requires that the compiler has already seen the template's
definition):
        <pre>
    template int add&lt;std::vector&lt;int&gt;, int&gt;
                    (std::vector&lt;int&gt; const &amp;vect, int const &amp;init);
</pre>
    <li> To disambiguate among multiple possibilities detected by the
compiler, explicit arguments may be used. For example:
        <pre>
    std::vector&lt;int&gt; vi;
    int sum = add&lt;std::vector&lt;int&gt;, int&gt;(vi, 0);
</pre>
    </ul>
<p>
<a name="l332"></a>
<h2>18.7: Specializing templates for deviating types</h2>
<a name="templatefunctions/specialization"></a>    The initial <code>add()</code> template, defining two identically typed parameters
works fine for all types sensibly supporting <code>operator+()</code> and a copy
constructor. However, these assumptions are not always met. For example, when
<code>char *</code>s are used, neither the <code>operator+()</code> nor the copy constructor is
(sensibly) available. The compiler does not know this, and will try to
instantiate the simple template function
        <pre>
    template &lt;typename Type&gt;
    Type add(Type const &amp;t1, Type const &amp;t2);
</pre>
    But it can't do so, since <code>operator+()</code> is not defined for pointers. In
situations like these it is clear that a match between the template's type
parameter(s) and the actually used type(s) is possible, but the standard
implementation is senseless or produces errors.
<p>
To solve this problem a <a name="an2600"></a>
<em>template explicit specialization</em> may be
defined.  A template explicit specialization defines the template function for
which a generic definition already exists, using specific actual template type
parameters.
<p>
In the abovementioned case an explicit specialization is required for a
<code>char const *</code>, but probably also for a <code>char *</code> type. Probably, as the
compiler still uses the standard type-deducing process mentioned earlier. So,
when our <code>add()</code> template function is specialized for <code>char *</code> arguments,
then its return type <em>must</em> also be a <code>char *</code>, whereas it <em>must</em> be a
<code>char const *</code> if the arguments are <code>char const *</code> values. In these cases
the template type parameter <code>Type</code> will be deduced properly. With <code>Type ==
char *</code>, for example, the head of the instantiated function becomes:
        <pre>
        char *add(char *const &amp;t1, char *const &amp;t2)
</pre>
    If this is considered undesirable, an <em>overloaded</em> version could be
designed expecting pointers. The following template function definition
expects two (<code>const</code>) pointers, and returns a non-const pointer:
        <pre>
    template &lt;typename T&gt;
    T *add(T const *t1, T const *t2)
    {
        std::cout &lt;&lt; "Pointers\n";
        return new T;
    }
</pre>
    But we might still not be where we want to be, as <em>this</em> overloaded
version will now only accept pointers to constant <code>T</code> elements. Pointers to
non-const <code>T</code> elements will not be accepted. At first sight it may come as a
surprise that the compiler will not apply a qualification transformation. But
there's no need for the compiler to do so: when non-const pointers are used
the compiler will simply use the initial definition of the <code>add()</code> template
function expecting any two arguments of equal types.
<p>
So do we have to define yet another overloaded version, expecting
non-const pointers? It is possible, but at some point it should become clear
that we're overshooting our goal. Like concrete functions and classes,
templates should have well-described purposes. Trying to add overloaded
template definitions to overloaded template definitions quickly turns the
template into a kludge. Don't follow this approach. A better approach is
probably to construct the template so that it fits its original purpose, make
allowances for the occasional specific case, and to describe its purpose
clearly in the template's documentation.
<p>
Nevertheless, there may be situations where a template explicit
specialization may be worth considering. Two specializations for <code>const</code> and
non-<code>const</code> pointers to characters might be considered for our <code>add()</code>
template function. Template explicit specializations are constructed as
follows:
    <ul>
    <li> They start with the keyword <code>template</code>.
    <li> Next, an empty set of angle brackets is written. This indicates to
the compiler that there must be an <em>existing</em> template whose prototype
matches the one we're about to define. If we err and there is no such template
        <a name="an2601"></a>

then the compiler reports an error like:
        <pre>
    error: template-id `add&lt;char*&gt;' for `char* add(char* const&amp;, char*
           const&amp;)' does not match any template declaration
</pre>
    <li> Next the head of the function is defined, which must follow the same
syntax as a template explicit instantiation declaration (see
section <a href="cplusplus18.html#TEMPFUNEXDEC">18.3.1</a>): it must specify the correct returntype, function
name, template type parameter explicitations, as well as the function's
parameter list.
    <li> The body of the function, definining the special implementation that
is required for the special actual template parameter types.
    </ul>
    Here are two  explicit specializations for the template function
<code>add()</code>, expecting <code>char *</code> and <code>char const *</code> arguments (note that the
<code>const</code> still appearing in the first template specialization is unrelated to
the specialized type (<code>char *</code>), but refers to the <code>const &amp;</code> mentioned in
the original template's definition. So, in this case it's a reference to a
constant pointer to a <code>char</code>, implying that the <code>char</code>s may be modified):
        <pre>
    template &lt;&gt; char *add&lt;char *&gt;(char * const &amp;p1,
                                        char * const &amp;p2)
    {
        std::string str(p1);
        str += p2;
        return strcpy(new char[str.length() + 1], str.c_str());
    }

    template &lt;&gt; char const *add&lt;char const *&gt;(char const *const &amp;p1,
                                        char const *const &amp;p2)
    {
        static std::string str;
        str = p1;
        str += p2;
        return str.c_str();
    }
</pre>
    Template explicit specializations are normally included in the file
containing the other template function's implementations.
<p>
A template explicit specialization can be declared in the usual way. I.e.,
by replacing its body with a semicolon.
<p>
Note in particular how important the pair of <a name="an2602"></a>
angle brackets are that
follow the <code>template</code> keyword when declaring a template explicit
specialization. If the angle brackets were omitted, we would have constructed
a
        <a name="an2603"></a>
template instantiation declaration.
    The compiler would silently process it, at the expense of a somewhat
longer compilation time.
<p>
When declaring a template explicit specialization (or when using an
instantiation declaration) the
        <a name="an2604"></a>

    explicit specification of the template type parameters can be omitted if
the compiler is able to deduce these types from the function's arguments.  As
this is the case with the <code>char (const) *</code> specializations, they could also
be declared as follows:
        <pre>
    template &lt;&gt; char const *add(char const *const &amp;p1,
                                        char const *const &amp;p2);
    template &lt;&gt; char const *add(char const *const &amp;p1,
                                        char const *const &amp;p2);
</pre>
    In addition, <code>template &lt;&gt;</code> could be omitted. However, this would remove
the template character from the declaration, as the resulting declaration is
now nothing but a plain function declaration. This is not an error: template
functions and non-template functions may overload each other. Ordinary
functions are not as restrictive as template functions with respect to allowed
type conversions. This could be a reason to overload a template with an
ordinary function every once in a while.
<p>
<a name="FUNCTIONSELECTION"></a><a name="l333"></a>
<h2>18.8: The template function selection mechanism</h2>
<a name="templatefunctions/selection"></a>    When the compiler encounters a function call, it must decide which
function to call when overloaded functions are available. In this section this
        <a name="an2605"></a>
 function selection mechanism is
described.
<p>
In our discussion, we assume that we ask the compiler to compile the
following <code>main()</code> function:
        <pre>
    int main()
    {
        double x = 12.5;
        add(x, 12.5);
    }
</pre>
    Furthermore we assume that the compiler has seen the following six
function declarations when it's about to compile <code>main()</code>:
        <pre>
    template &lt;typename Type&gt;                                    // function 1
    Type add(Type const &amp;lvalue, Type const &amp;rvalue);

    template &lt;typename Type1, typename Type2&gt;                   // function 2
    Type1 add(Type1 const &amp;lvalue, Type2 const &amp;rvalue);

    template &lt;typename Type1, typename Type2, typename Type3&gt;   // function 3
    Type1 add(Type1 const &amp;lvalue, Type1 const &amp;mvalue, Type2 const &amp;rvalue);

    double add(float lvalue, double rvalue);                    // function 4
    double add(std::vector&lt;double&gt; const &amp;vd);                  // function 5
    double divide(double lvalue, double rvalue);                // function 6
</pre>
    The compiler, having read <code>main()</code>'s statement, must now decide which
function must actually be called. It proceeds as follows:
    <ul>
    <li> First, a set of <a name="an2606"></a>
<em>candidate functions</em> is constructed. This set
contains all functions that:
        <ul>
        <li> are <a name="an2607"></a>
visible at the point of the call;
        <li> have the same names as the called function.
        </ul>
        As function 6 has a different name, it is removed from the set. The
compiler is left with a set of five candidate functions: 1 until 5.
    <li> Second, the set of <a name="an2608"></a>
<em>viable functions</em> is constructed. Viable
functions are functions for which <a name="an2609"></a>
type conversions exist that can be
applied to match the types of the parameters of the functions and the types of
the actual arguments. This implies that the number of arguments must match the
number of parameters of the viable functions.
    <li> As functions 3 and 5 have different numbers of parameters they are
removed from the set.
    <li> Now let's `play compiler' to decide among the remaining functions 1,
2 and 4. This is done by assigning <em>penalty points</em> to the remaining
functions. Eventually the function having the smallest score will be
selected. A point is assigned for every standard argument deduction process
transformation that is required (so, for every <em>lvalue-, qualification-</em>, or
<em>derived-to-base class</em> transformation that is applied).
    <li> Eventually multiple functions might emerge at the top. Even though we
have a draw in this case, the compiler will not always report an ambiguity. As
we've seen before, a more specialized function is selected over a more general
function. So, if a template explicit specialization and its more general
variant appear at the top, the specialization is selected. Similarly, a
concrete function will be selected over a template function (but remember:
only if both appear at the top of the ranking process).
    <li> As a <a name="an2610"></a>
rule of thumb we have:
        <ul>
        <li> when there are multiple viable functions at the top of the set of
viable functions, then the plain function template instantiations are
removed;
        <li> if multiple functions remain, template explicit specializations
are removed;
        <li> if only one function remains, it is selected;
        <li> otherwise, the compiler can't decide and reports an error: the
call is ambiguous.
        </ul>
    </ul>
    Now we'll apply the above procedure to the viable functions 1, 2 and 4.
As we will find function 1 to contain a slight complication, we'll start with
function 2.
    <ul>
    <li> Function 2 has prototype:
        <pre>
    template &lt;typename T1, typename T2&gt;
    T1 add(T1 const &amp;a, T2 const &amp;b);
</pre>
    The function is called as <code>add(x, 12.5)</code>. As <code>x</code> is a <code>double</code> both
<code>T &amp;x</code> and <code>T const &amp;x</code> would be acceptable, albeit that <code>T const &amp;x</code>
will require a qualification transformation. Since the function's prototype
uses <code>T const &amp;</code> a qualification transformation is needed. The function is
charged 1 point, and tf(T1) is now determined as <code>double</code>.
<p>
Next, 12.5 is recognized as a <code>double</code> as well (note that <code>float</code>
constants are recognized by their `F' suffix, e.g., 12.5F), and it is also a
constant value. So, without transformations, we find <code>12.5 == T2 const &amp;</code>
and at no charge <code>T1</code> is recognized as <code>double</code> as well.
    <li> Function 4 has prototype:
        <pre>
    double add(float lvalue, double rvalue);
</pre>
    Although it is called as <code>add(x, 12.5)</code> with <code>x</code> being of type
<code>double</code>; but a standard conversion exists from type <code>double</code> to type
<code>float</code>. Furthermore, 12.5 is a <code>double</code>, which can be used to initialize
<code>rvalue</code>.
    </ul>
    Thus, at this point we could ask the compiler to select among:
        <pre>
    add(double const &amp;, double const &amp;b);
</pre>
    and
        <pre>
    add(float, double);
</pre>
    This does not involve `template function selection' since the first one
has already been determined. As the first function doesn't require any
standard conversion at all, it is selected, since a perfect match is selected
over one requiring a standard conversion.
<p>
As an intermezzo you are invited to take a closer look at this process by
defining <code>float x</code> instead of <code>double x</code>, or by defining <code>add(float x,
double x)</code> as add(double x, double x): in these cases the template function
has the same prototype as the non-template function, and so the non-template
function is selected since it's a more specific function. Earlier we've seen
that process in action when redefining <code>ostream::operator&gt;&gt;(ostream &amp;os,
string &amp;str)</code> as a non-template function.
<p>
Now it's time to go back to  template function 1.
    <ul>
    <li> Function 1 has prototype:
        <pre>
    template &lt;typename T&gt;
    T add(T const &amp;t1, T const &amp;t2);
</pre>
    Once again we call <code>add(x, 12.5)</code> and will deduce template types. In
this case there's only one template type parameter T.  Let's start with the
first parameter:
        <ul>
        <li> The argument <code>x</code> is of type <code>double</code>, so both <code>T &amp;x</code> and
<code>T const &amp;x</code> are acceptable. Acoording to the function's parameter list <code>T
const &amp;x</code> must be used, which requires a qualification transformation. So
we'll charge the function 1 point and T is determined as <code>double</code>.  This
results in the instantiation of
        <pre>
    add(double const &amp;t1, double const &amp;t2)
</pre>
    allowing us to call, at the expense of 1 point, <code>add(x, 12.5)</code>.
        </ul>
    But we can do better by starting our deduction process at the <em>second</em>
parameter:
        <ul>
        <li> Since 12.5 is a constant <code>double</code> value we see that <code>12.5 == T
const &amp;</code>. So we conclude (free of charge) that T is <code>double</code>. Our function
becomes
        <pre>
    add(double const &amp;t1, double const &amp;t2)
</pre>
allowing us to call <code>add(x, 12.5)</code>.
        </ul>
    </ul>
    Earlier this section, we preferred  function 2 over function 4. Function 2
is a template function that required one qualification
transformation. Function 1, on the other hand, did not require any
transformation at all, so it emerges as the function to be used.
<p>
As an <a name="an2611"></a>
exercise, feed the above six declarations and <code>main()</code> to the
compiler and wait for the linker errors: the linker will complain that the
(template) function
        <pre>
    double add&lt;double&gt;(double const&amp;, double const&amp;)
</pre>
    is an <a name="an2612"></a>
undefined reference.
<p>
<a name="NAMERESFUN"></a><a name="l334"></a>
<h2>18.9: Compiling template definitions and instantiations</h2>
<a name="templatefunctions/nameresolution"></a>    Consider the following definition of the <code>add()</code> template function:
        <pre>
    template &lt;typename Container, typename Type&gt;
    Type add(Container const &amp;container, Type init)
    {
        return std::accumulate(container.begin(), container.end(), init);
    }
</pre>
    In this template definition, <code>std::accumulate()</code> is called, using
<code>container</code>'s <code>begin()</code> and <code>end()</code> members.
<p>
The calls <code>container.begin()</code> and <code>container.end()</code> are said to
        <a name="an2613"></a>

    <em>depend on template type parameters</em>. The compiler, not having seen
<code>container</code>'s interface, cannot check whether <code>container</code> will actually
have members <code>begin()</code> and <code>end()</code> returning input iterators, as required
by <code>std::accumulate</code>.
<p>
On the other hand, <code>std::accumulate()</code> itself is a function call which
is independent of any template type parameter. Its <em>arguments</em> are dependent
of template parameters, but the function call itself isn't. Statements in a
template's body that are independent of template type parameters are said
<em>not to depend on template type parameters</em>.
<p>
When the compiler reads a template definition, it will verify
the syntactical correctness of all statements not depending on template type
parameters. I.e., it must have seen all class definitions, all type
definitions, all function declarations etc., that are used in the statements
not depending on the template's type parameters. If this condition isn't met,
the compiler will not accept the template's definition. Consequently, when
defining the above template, the header file <code>numeric</code> must have been
included first, as this header file declares <code>std::accumulate()</code>.
<p>
On the other hand, with statements depending on template type parameters
the compiler cannot perform these extensive checks, as it has, for example,
no way to verify the existence of a member <code>begin()</code> for the as yet
unspecified type <code>Container</code>. In these cases the compiler will perform
superficial checks, assuming that the required members, operators and types
will eventually become available.
<p>
The location in the program's source where the template is instantiated is
        <a name="an2614"></a>

        <a name="an2615"></a>
 called its <em>point of instantiation</em>. At
the point of instantiation the compiler will deduce the actual types of the
template's type parameters. At that point it will check the syntactical
correctness of the template's statements that depend on template type
parameters. This implies that <em>only at the point of instantiation</em> the
required declarations must have been read by the compiler.  As a
        <a name="an2616"></a>
rule of thumb,
    make sure that all required declarations (usually: header files) have been
read by the compiler at every point of instantiation of the template. For the
template's definition itself a more relaxed requirement can be
formulated. When the definition is read only the declarations required for
statements <em>not</em> depending on the template's type parameters must be known.
<p>
<a name="l335"></a>
<h2>18.10: Summary of the template declaration syntax</h2>
<a name="templatefunctions/summary"></a>In this section the basic syntactical constructions when declaring templates
are summarized. When <em>defining</em> templates, the terminating
semicolon should be replaced by a function body. However, not every template
declaration may be converted into a template definition. If a definition may
be provided it is explicitly mentioned.
    <ul>
    <li> A plain template declaration (a definition is possible):
        <pre>
    template &lt;typename Type1, typename Type2&gt;
    void function(Type1 const &amp;t1, Type2 const &amp;t2);
</pre>
    <li> A template instantiation declaration (no definition):
        <pre>
    template
    void function&lt;int, double&gt;(int const &amp;t1, double const &amp;t2);
</pre>
    <li> A template using explicit types (no definition):
        <pre>
    void (*fp)(double, double) = function&lt;double, double&gt;;
    void (*fp)(int, int) = function&lt;int, int&gt;;
</pre>
    <li> A template specialization (a definition is possible):
        <pre>
    template &lt;&gt;
    void function&lt;char *, char *&gt;(char *const &amp;t1, char *const &amp;t2);
</pre>
    <li> A template declaration declaring friend template functions within
        <a name="an2617"></a>

template classes (covered in section <a href="cplusplus19.html#TEMPFRIENDS">19.8</a>):
        <pre>
    friend void function&lt;Type1, Type2&gt;(parameters);
</pre>
    </ul>
<p>

<hr>
<ul>
    <li> <a href="cplusplus.html">Table of Contents</a>
    <li> <a href="cplusplus17.html">Previous Chapter</a>
    <li> <a href="cplusplus19.html">Next Chapter</a>
</ul>
<hr>
</body>
</html>
